JZ63 数据流中的中位数

https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

注意：PriorityQueue 默认是从小到大排序

这一题主要的思想是利用优先队列，优先队列分为大顶堆和小顶堆，默认维护的是小顶堆的优先队列。

需要求的是中位数，如果我将 1 2 3 4 5 6 7 8定为最终的数据流 此时的中位数是 4 + 5 求均值。为什么是 4，为什么是 5 利用队列我们就可以看得很清楚，4 是前半部分最大的值，肯定是维系在大顶堆 而 5 是后半部分的最小值，肯定是维系在小顶堆。

问题就好理解了： 使用小顶堆存大数据，使用大顶堆存小数据。这样堆顶一取出就是中位数了。

import java.util.*;
 
public class Solution {
    // 代表排序后的左半部分 // 5 6 7 8
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    // 代表排序后的右半部分 // 4 3 2 1
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
 
    // 时间复杂度O(logn)
    public void Insert(Integer num) {
        // 平均分配，元素个数为奇数时插入到maxHeap，为偶数时插入到minHeap
        if ((minHeap.size() + maxHeap.size()) % 2 == 1) {
            // 若num完全小于minHeap的所有元素，直接将num插入maxHeap即可
            // 若num大于minHeap中的一些元素，则将num插入minHeap, 然后移除minHeap的最小值，将其插入maxHeap
            if (!minHeap.isEmpty() && num > minHeap.element()) {
                minHeap.add(num);
                num = minHeap.remove();
            }
            maxHeap.add(num);
        } else {
            // 若num完全大于maxHeap的所有元素，直接将num插入minHeap即可
            // 若num小于maxHeap中的一些元素，则将num插入maxHeap，然后移除maxHeap的最大值，将其插入minHeap
            if (!maxHeap.isEmpty() && num < maxHeap.element()) {
                maxHeap.add(num);
                num = maxHeap.remove();
            }
            minHeap.add(num);
        }
    }
 
    // 时间复杂度O(1)
    public Double GetMedian() {
        int size = maxHeap.size() + minHeap.size();
        if (size % 2 == 1) {
            return minHeap.element() * 1.0;
        } else {
            return (maxHeap.element() + minHeap.element()) / 2.0;
        }
    }
 
}